<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
      <title>GTL - Graph Template Library: min_tree Class Reference</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li class="current"><a href="classes.html"><span>Classes</span></a></li>
    <li><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<div class="tabs">
  <ul>
    <li><a href="classes.html"><span>Alphabetical&nbsp;List</span></a></li>
    <li><a href="annotated.html"><span>Class&nbsp;List</span></a></li>
    <li><a href="hierarchy.html"><span>Class&nbsp;Hierarchy</span></a></li>
    <li><a href="functions.html"><span>Class&nbsp;Members</span></a></li>
  </ul>
</div>
<h1>min_tree Class Reference</h1><!-- doxytag: class="min_tree" --><!-- doxytag: inherits="algorithm" -->Kruskal's algorithm for finding minimal spanning tree of a graph.  
<a href="#_details">More...</a>
<p>
<div class="dynheader">
Inheritance diagram for min_tree:</div>
<div class="dynsection">
<p><center><img src="a00169.gif" border="0" usemap="#a00170" alt="Inheritance graph"></center>
<map name="a00170">
<area shape="rect" href="a00001.html" title="Abstract baseclass for all algoritm&#45;classes." alt="" coords="5,7,83,31"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>
<div class="dynheader">
Collaboration diagram for min_tree:</div>
<div class="dynsection">
<p><center><img src="a00171.gif" border="0" usemap="#a00172" alt="Collaboration graph"></center>
<map name="a00172">
<area shape="rect" href="a00001.html" title="Abstract baseclass for all algoritm&#45;classes." alt="" coords="5,84,83,108"><area shape="rect" href="a00011.html" title="edge_map\&lt; int \&gt;" alt="" coords="107,84,229,108"><area shape="rect" title="dist" alt="" coords="152,105,160,113"><area shape="rect" title="dist" alt="" coords="92,171,100,179"><area shape="rect" href="a00019.html" title="ne_map\&lt; edge, int, graph, allocator\&lt; int \&gt; \&gt;" alt="" coords="27,7,309,31"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>

<p>
<a href="a00173.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="d5c01151dac766b65b485b73da5f1543"></a><!-- doxytag: member="min_tree::min_tree" ref="d5c01151dac766b65b485b73da5f1543" args="()" -->
&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html#d5c01151dac766b65b485b73da5f1543">min_tree</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Constructor. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="0df992f77a8656121777aa2c0380a67a"></a><!-- doxytag: member="min_tree::~min_tree" ref="0df992f77a8656121777aa2c0380a67a" args="()" -->
virtual&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html#0df992f77a8656121777aa2c0380a67a">~min_tree</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Destructor. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html#d87b1bfbc687ad943c07538fa0c3d270">check</a> (<a class="el" href="a00014.html">graph</a> &amp;g)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Checks whether algorithm can be applied.  <a href="#d87b1bfbc687ad943c07538fa0c3d270"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html#c025e8dad0db7a6a1e0e7b476b547802">run</a> (<a class="el" href="a00014.html">graph</a> &amp;g)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Applies algorithm to graph g.  <a href="#c025e8dad0db7a6a1e0e7b476b547802"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html#3c4b17c455dd77b4120ec5564a4ac428">reset</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Resets algorithm.  <a href="#3c4b17c455dd77b4120ec5564a4ac428"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html#0f3eb1714b7859576037cf4b991b16cb">set_distances</a> (const <a class="el" href="a00011.html">edge_map</a>&lt; int &gt; &amp;dist)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Sets edge weights.  <a href="#0f3eb1714b7859576037cf4b991b16cb"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">set&lt; <a class="el" href="a00010.html">edge</a> &gt;&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html#59de5032f3ff973f97f29d43f70ea360">get_min_tree</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Edges of minimal spanning tree calculated in the last call of <a class="el" href="a00018.html#c025e8dad0db7a6a1e0e7b476b547802" title="Applies algorithm to graph g.">min_tree::run</a>.  <a href="#59de5032f3ff973f97f29d43f70ea360"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00018.html#8ca03d32ba55a9eb20b52fcb0e6fa6a5">get_min_tree_length</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Weight of minimal spanning tree.  <a href="#8ca03d32ba55a9eb20b52fcb0e6fa6a5"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
Kruskal's algorithm for finding minimal spanning tree of a graph. 
<p>
<dl class="author" compact><dt><b>Author:</b></dt><dd>Marcus Raitner </dd></dl>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="d87b1bfbc687ad943c07538fa0c3d270"></a><!-- doxytag: member="min_tree::check" ref="d87b1bfbc687ad943c07538fa0c3d270" args="(graph &amp;g)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int min_tree::check           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>g</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Checks whether algorithm can be applied. 
<p>
The graph must<ul>
<li>be undirected</li><li>be connected</li><li>have more than 2 nodes</li></ul>
<p>
Additionally the weights of the edges must have been set in advance using <a class="el" href="a00018.html#0f3eb1714b7859576037cf4b991b16cb" title="Sets edge weights.">min_tree::set_distances</a>.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>g</em>&nbsp;</td><td><a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> </td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b">algorithm::GTL_OK</a> if algorithm can be applied <a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7">algorithm::GTL_ERROR</a> otherwise. </dd></dl>

<p>Implements <a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed">algorithm</a>.</p>

</div>
</div><p>
<a class="anchor" name="c025e8dad0db7a6a1e0e7b476b547802"></a><!-- doxytag: member="min_tree::run" ref="c025e8dad0db7a6a1e0e7b476b547802" args="(graph &amp;g)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int min_tree::run           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>g</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Applies algorithm to graph g. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>g</em>&nbsp;</td><td>graph </td></tr>
  </table>
</dl>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b">algorithm::GTL_OK</a></em>&nbsp;</td><td>on success </td></tr>
    <tr><td valign="top"></td><td valign="top"><em><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7">algorithm::GTL_ERROR</a></em>&nbsp;</td><td>otherwise </td></tr>
  </table>
</dl>

<p>Implements <a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca">algorithm</a>.</p>

</div>
</div><p>
<a class="anchor" name="3c4b17c455dd77b4120ec5564a4ac428"></a><!-- doxytag: member="min_tree::reset" ref="3c4b17c455dd77b4120ec5564a4ac428" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void min_tree::reset           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Resets algorithm. 
<p>
Prepares the algorithm to be applied to another graph. <em>Please</em> <em>note:</em> The options an algorithm may support do <em>not</em> get reset by this. It is just to reset internally used datastructures. 
<p>Implements <a class="el" href="a00001.html#21aba63d066ae7897de6ca7d8425c408">algorithm</a>.</p>

</div>
</div><p>
<a class="anchor" name="0f3eb1714b7859576037cf4b991b16cb"></a><!-- doxytag: member="min_tree::set_distances" ref="0f3eb1714b7859576037cf4b991b16cb" args="(const edge_map&lt; int &gt; &amp;dist)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void min_tree::set_distances           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00011.html">edge_map</a>&lt; int &gt; &amp;&nbsp;</td>
          <td class="paramname"> <em>dist</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Sets edge weights. 
<p>
Setting of edge weights must be done before calling <a class="el" href="a00018.html#d87b1bfbc687ad943c07538fa0c3d270" title="Checks whether algorithm can be applied.">min_tree::check</a> and <a class="el" href="a00018.html#c025e8dad0db7a6a1e0e7b476b547802" title="Applies algorithm to graph g.">min_tree::run</a>.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>dist</em>&nbsp;</td><td>edge weigths. </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="59de5032f3ff973f97f29d43f70ea360"></a><!-- doxytag: member="min_tree::get_min_tree" ref="59de5032f3ff973f97f29d43f70ea360" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">set&lt;<a class="el" href="a00010.html">edge</a>&gt; min_tree::get_min_tree           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Edges of minimal spanning tree calculated in the last call of <a class="el" href="a00018.html#c025e8dad0db7a6a1e0e7b476b547802" title="Applies algorithm to graph g.">min_tree::run</a>. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>Set of edges of representing the minimal spanning tree </dd></dl>

</div>
</div><p>
<a class="anchor" name="8ca03d32ba55a9eb20b52fcb0e6fa6a5"></a><!-- doxytag: member="min_tree::get_min_tree_length" ref="8ca03d32ba55a9eb20b52fcb0e6fa6a5" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int min_tree::get_min_tree_length           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Weight of minimal spanning tree. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>weight of minimal spanning tree. </dd></dl>

</div>
</div><p>
    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>
